{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Next Greater Node In Linked List"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #linked-list #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #链表 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: nextLargerNodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #链表中的下一个更大节点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个长度为&nbsp;<code>n</code>&nbsp;的链表&nbsp;<code>head</code></p>\n",
    "\n",
    "<p>对于列表中的每个节点，查找下一个 <strong>更大节点</strong> 的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值 <strong>严格大于</strong> 它的值。</p>\n",
    "\n",
    "<p>返回一个整数数组 <code>answer</code> ，其中 <code>answer[i]</code> 是第 <code>i</code> 个节点( <strong>从1开始</strong> )的下一个更大的节点的值。如果第 <code>i</code> 个节点没有下一个更大的节点，设置&nbsp;<code>answer[i] = 0</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/08/05/linkedlistnext1.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [2,1,5]\n",
    "<strong>输出：</strong>[5,5,0]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/08/05/linkedlistnext2.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [2,7,4,3,5]\n",
    "<strong>输出：</strong>[7,0,5,5,0]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>链表中节点数为&nbsp;<code>n</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= Node.val &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [next-greater-node-in-linked-list](https://leetcode.cn/problems/next-greater-node-in-linked-list/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [next-greater-node-in-linked-list](https://leetcode.cn/problems/next-greater-node-in-linked-list/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,1,5]', '[2,7,4,3,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverse(self,head):\n",
    "            pre=None\n",
    "            cur=head\n",
    "            while cur:\n",
    "                temp=cur.next\n",
    "                cur.next=pre\n",
    "                pre=cur\n",
    "                cur=temp\n",
    "            return pre\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        node=self.reverse(head)\n",
    "        ans=[]\n",
    "        st=[]\n",
    "        while node:\n",
    "            while st and st[-1]<=node.val:\n",
    "                st.pop()\n",
    "            ans.append(st[-1] if st else 0)\n",
    "            st.append(node.val)\n",
    "            node=node.next\n",
    "        #因为是倒着记录的所以也要把答案反转\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        #翻转链表\n",
    "        #为什么要翻转？\n",
    "        #从左往右没法对ans的位置进行很好的计数\n",
    "        pre = None\n",
    "        cur = head\n",
    "        while cur:\n",
    "            nxt = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = nxt\n",
    "        node = pre   #翻转后的头节点\n",
    "\n",
    "        ans = []\n",
    "        st = []\n",
    "        while node:\n",
    "            val = node.val\n",
    "            while st and val >= st[-1]:\n",
    "                st.pop()\n",
    "            if not st:ans.append(0)\n",
    "            else:ans.append(st[-1])\n",
    "            st.append(val)\n",
    "            node = node.next\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverse(self,head):\n",
    "            pre=None\n",
    "            cur=head\n",
    "            while cur:\n",
    "                temp=cur.next\n",
    "                cur.next=pre\n",
    "                pre=cur\n",
    "                cur=temp\n",
    "            return pre\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        node=self.reverse(head)\n",
    "        ans=[]\n",
    "        st=[]\n",
    "        while node:\n",
    "            while st and st[-1]<=node.val:\n",
    "                st.pop()\n",
    "            ans.append(st[-1] if st else 0)\n",
    "            st.append(node.val)\n",
    "            node=node.next\n",
    "        #因为是倒着记录的所以也要把答案反转\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        def reverse(head:ListNode):\n",
    "            cur,pre,length = head,None,0\n",
    "            while cur :\n",
    "                length += 1\n",
    "                nxt = cur.next\n",
    "                cur.next = pre\n",
    "                pre = cur\n",
    "                cur = nxt\n",
    "            return pre,length\n",
    "        reverseHead,n = reverse(head)\n",
    "        ans,cur,stack = [0] * n,reverseHead.next,[reverseHead.val]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            while stack and cur.val >= stack[-1]:\n",
    "                stack.pop()\n",
    "            if not stack:\n",
    "                ans[i] = 0\n",
    "            else :\n",
    "                ans[i] = stack[-1]\n",
    "            stack.append(cur.val)\n",
    "            cur = cur.next\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        node = head\n",
    "        n = 0\n",
    "        while node != None:\n",
    "            node = node.next\n",
    "            n += 1\n",
    "        head = self.reverseList(head)\n",
    "        stack = []\n",
    "        ans = [0] * n\n",
    "        node = head\n",
    "        for i in range(n):\n",
    "            while stack != [] and node.val >= stack[-1]:\n",
    "                stack.pop()\n",
    "            if stack != []:\n",
    "                ans[n - i - 1] = stack[-1]\n",
    "            stack.append(node.val)\n",
    "            node = node.next\n",
    "        return ans\n",
    "\n",
    "    def reverseList(self, head):\n",
    "        new_head = head\n",
    "        while head.next != None:\n",
    "            temp = head.next\n",
    "            head.next = temp.next\n",
    "            temp.next = new_head\n",
    "            new_head = temp\n",
    "        return new_head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        res = []\n",
    "        i = 0\n",
    "        st = []\n",
    "        while head :\n",
    "            res.append(0)\n",
    "            while st and st[-1][0] < head.val :\n",
    "               _, idx = st.pop()\n",
    "               res[idx] = head.val\n",
    "            st.append([head.val, i])\n",
    "            i += 1\n",
    "            head = head.next\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        res = []\n",
    "        i = 0\n",
    "        st = []\n",
    "        while head :\n",
    "            res.append(0)\n",
    "            while st and st[-1][0] < head.val :\n",
    "               _, idx = st.pop()\n",
    "               res[idx] = head.val\n",
    "            st.append([head.val, i])\n",
    "            i += 1\n",
    "            head = head.next\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        nums = []\n",
    "        while head:\n",
    "            nums.append(head.val)\n",
    "            head = head.next\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        ans = [0] * n\n",
    "\n",
    "        stack = []\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while stack and stack[-1] <= nums[i]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                ans[i] = stack[-1]\n",
    "            stack.append(nums[i])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        lst = [0 for i in range(10001)]\n",
    "        num = []\n",
    "        idx = []\n",
    "        i = 0\n",
    "        while head is not None:\n",
    "            while num and head.val > num[len(num)-1]:\n",
    "                lst[idx[len(num)-1]] = head.val\n",
    "                idx.pop(len(num)-1)\n",
    "                num.pop(len(num)-1)\n",
    "            num.append(head.val)\n",
    "            idx.append(i)\n",
    "            i += 1\n",
    "            head = head.next\n",
    "        return lst[0:i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        ans = [0]\n",
    "        cache = dict()\n",
    "        cache[head.val] = [0]\n",
    "        cur = head.next\n",
    "        stack = [head.val]\n",
    "        while cur:\n",
    "            val = cur.val\n",
    "            while stack and val > stack[-1]:\n",
    "                p = stack.pop()\n",
    "                if p in cache:\n",
    "                    for i in cache[p]:\n",
    "                        ans[i] = val\n",
    "                    del cache[p]\n",
    "            stack.append(val)\n",
    "            ans.append(0)\n",
    "            if val in cache:\n",
    "                cache[val].append(len(ans) - 1)\n",
    "            else:\n",
    "                cache[val] = [len(ans) - 1]\n",
    "            cur = cur.next\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        arr=[]\n",
    "        min=0\n",
    "        while head:\n",
    "            arr.append(head.val)\n",
    "            head=head.next\n",
    "        dic={}\n",
    "        min=0\n",
    "        res=[0]*len(arr)\n",
    "        for i in range(1,len(arr)):\n",
    "            if arr[i]>arr[i-1]:\n",
    "                res[i-1]=arr[i]\n",
    "            else:\n",
    "                dic[i-1]=arr[i-1]\n",
    "                if min>arr[i-1]:\n",
    "                    min=arr[i-1]\n",
    "            if arr[i]>min and len(dic.keys())!=0:\n",
    "                temp=10**(9)+1\n",
    "                for j in list(dic):\n",
    "                    if dic[j]<arr[i]:\n",
    "                        res[j]=arr[i]\n",
    "                        del dic[j]\n",
    "                    elif arr[i]<=dic[j]<temp:\n",
    "                        temp=dic[j]\n",
    "                min=temp\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        # value栈\n",
    "        stack = []\n",
    "        # 位置栈\n",
    "        stack_pos = []\n",
    "        ans = {}\n",
    "        cur = head\n",
    "        i = 0\n",
    "        while cur:\n",
    "            # 比较栈顶\n",
    "            while stack and cur.val > stack[-1]:\n",
    "                ans[stack_pos[-1]] = cur.val\n",
    "                stack_pos.pop()\n",
    "                stack.pop()\n",
    "            stack_pos.append(i)\n",
    "            stack.append(cur.val)\n",
    "            ans[i] = 0\n",
    "            i += 1\n",
    "            cur = cur.next\n",
    "        return [ans[j] for j in range(i)]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        # value栈\n",
    "        stack = []\n",
    "        # 位置栈\n",
    "        stack_pos = []\n",
    "        ans = {}\n",
    "        cur = head\n",
    "        i = 0\n",
    "        while cur:\n",
    "            # 比较栈顶\n",
    "            while stack and cur.val > stack[-1]:\n",
    "                ans[stack_pos[-1]] = cur.val\n",
    "                stack_pos.pop()\n",
    "                stack.pop()\n",
    "            stack_pos.append(i)\n",
    "            stack.append(cur.val)\n",
    "            ans[i] = 0\n",
    "            i += 1\n",
    "            cur = cur.next\n",
    "        return [ans[j] for j in range(i)]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        ls = []     # 存储找到下一个更大节点的节点编号和更大值{id, greaterVal}\n",
    "        stack = []  # 单调栈，存储还没有找到下一个更大节点的节点编号和节点值{id, val}\n",
    "        node = head\n",
    "        n = 0       # 统计元素个数\n",
    "        # 遍历链表\n",
    "        while node is not None:\n",
    "            # 栈不为空且栈顶节点值小于当前节点值\n",
    "            # 当前节点值是栈顶节点的下一个更大节点，弹出栈顶元素\n",
    "            while len(stack) > 0 and stack[-1][1] < node.val:\n",
    "                ls.append([stack.pop()[0], node.val])\n",
    "            stack.append([n, node.val]) # 将当前节点压入栈，它是当前栈内的最小值\n",
    "            n += 1  # 更新计数\n",
    "            node = node.next    # 更新下一个节点\n",
    "\n",
    "        answer = [0,] * n\n",
    "        for p in ls:\n",
    "            # list列表中每个二元数组都存储编号为point[0]的节点的下一个更大节点值point[1]\n",
    "            # 编号不在list中的节点就是没有下一个更大节点值，默认为0\n",
    "            answer[p[0]] = p[1]\n",
    "        \n",
    "        return answer \n",
    "             \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        cur = c = head\n",
    "        total = 0\n",
    "        while cur:\n",
    "            total+=1\n",
    "            cur = cur.next\n",
    "        ans= [0]*total\n",
    "        stack = []\n",
    "        caculation = 0\n",
    "        while c:\n",
    "            while stack and stack[-1][1]<c.val:\n",
    "                j = stack.pop()[0]\n",
    "                ans[j] = c.val\n",
    "            stack.append((caculation,c.val))\n",
    "            caculation+=1\n",
    "            c = c.next\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        n = 0\n",
    "        root = head\n",
    "        while root:\n",
    "            n += 1\n",
    "            root = root.next\n",
    "        ans = [0] * n\n",
    "        stack = []\n",
    "        root = head\n",
    "        i = 0\n",
    "        while root:\n",
    "            while stack and stack[-1][0] < root.val:\n",
    "                ans[stack[-1][1]] = root.val\n",
    "                stack.pop()\n",
    "            stack.append((root.val, i))\n",
    "            i += 1\n",
    "            root = root.next\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        values_list = []\n",
    "        pre = head\n",
    "        while pre:\n",
    "            values_list.append(pre.val)\n",
    "            pre = pre.next\n",
    "        ans = [0] * len(values_list)\n",
    "        st = []\n",
    "        for i in range(len(values_list)):\n",
    "            while st and values_list[i] > values_list[st[-1]]:\n",
    "                index = st.pop()\n",
    "                ans[index] = values_list[i]\n",
    "            st.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        nums = []\n",
    "        while head is not None:\n",
    "            nums.append(head.val)\n",
    "            head = head.next\n",
    "        n = len(nums)\n",
    "        res = [0] * n\n",
    "        stack = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while len(stack) != 0 and nums[stack[-1]] <= nums[i]:\n",
    "                stack.pop()\n",
    "            if len(stack) != 0:\n",
    "                res[i] = nums[stack[-1]]\n",
    "            stack.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        ans = []\n",
    "        st = []  # 单调栈（节点下标）\n",
    "        while head:\n",
    "            while st and ans[st[-1]] < head.val:\n",
    "                ans[st.pop()] = head.val  # ans[st.pop()] 后面不会再访问到了\n",
    "            st.append(len(ans))  # 当前 ans 的长度就是当前节点的下标\n",
    "            ans.append(head.val)\n",
    "            head = head.next\n",
    "        for i in st:\n",
    "            ans[i] = 0  # 没有下一个更大元素\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        cur = head\n",
    "        tmp = []\n",
    "        res = []\n",
    "        n = 0\n",
    "        while cur.next:\n",
    "            if cur.next.val > cur.val:\n",
    "                res.append(cur.next.val)\n",
    "\n",
    "                while tmp:\n",
    "                    if tmp[-1][1] < cur.next.val:\n",
    "                        res[tmp[-1][0]] = cur.next.val\n",
    "                        tmp.pop()\n",
    "                    else:\n",
    "                        break\n",
    "\n",
    "            else:\n",
    "                res.append(0)\n",
    "                tmp.append((n, cur.val))\n",
    "            cur = cur.next\n",
    "            n += 1\n",
    "        res.append(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        if not head:\n",
    "            return []\n",
    "        stack=[(head.val, 0)] # 单调栈\n",
    "        head=head.next\n",
    "        res={}\n",
    "        i=1\n",
    "        while head:\n",
    "            v = head.val\n",
    "            while stack and stack[-1][0] < v:\n",
    "                _, k = stack.pop()\n",
    "                res[k]=v\n",
    "            stack.append((v, i))\n",
    "            head, i = head.next, i+1\n",
    "        for _, k in stack:\n",
    "            res[k]=0\n",
    "        return [res[i] for i in range(len(res))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        from collections import defaultdict\n",
    "        trace = defaultdict(int)\n",
    "        stack = []\n",
    "        i = 0\n",
    "        while head:\n",
    "            while stack and stack[-1][1] < head.val:\n",
    "                lastIdx, _ = stack.pop()\n",
    "                trace[lastIdx] = head.val\n",
    "            stack.append((i, head.val))\n",
    "            i += 1\n",
    "            head = head.next\n",
    "        ret = []\n",
    "        for j in range(i):\n",
    "            ret.append(trace[j])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        stk=[]\n",
    "        p=head\n",
    "        ans=[0]*100010\n",
    "        i=0\n",
    "        while p:\n",
    "            while stk and stk[-1][0]<p.val:\n",
    "                ans[stk[-1][1]]=p.val\n",
    "                stk.pop()\n",
    "            stk.append((p.val,i))\n",
    "            i+=1\n",
    "            p=p.next\n",
    "        return ans[:i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        ans = [0] * (100001)\n",
    "        st = []\n",
    "        cnt = 0\n",
    "        while head:\n",
    "            while st and st[-1][1].val < head.val:\n",
    "                j = st.pop()[0]\n",
    "                print(j)\n",
    "                ans[j] = head.val\n",
    "            st.append((cnt,head))\n",
    "            head = head.next\n",
    "            cnt += 1\n",
    "            # print(st[-1][1].val)\n",
    "        return ans[:cnt]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        head.pre = None\n",
    "        # 走到底，同时构建双向链表\n",
    "        while n := head.next:\n",
    "            n.pre = head\n",
    "            head = n\n",
    "        \n",
    "        ans = [0]\n",
    "        while p := head.pre:\n",
    "            if p.val < head.val:\n",
    "                ans.append(head.val)\n",
    "            else:\n",
    "                cur = p.next\n",
    "                while cur:\n",
    "                    if cur.val > p.val:\n",
    "                        ans.append(cur.val)\n",
    "                        break\n",
    "                    cur = cur.next\n",
    "                else:\n",
    "                    ans.append(0)\n",
    "                p.next = cur    # 至关重要，缩短路径\n",
    "            head = p\n",
    "\n",
    "        ans.reverse()\n",
    "        return ans\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        head.pre = None\n",
    "        # 走到底，同时构建双向链表\n",
    "        while n := head.next:\n",
    "            n.pre = head\n",
    "            head = n\n",
    "        \n",
    "        ans = [0]\n",
    "        while p := head.pre:\n",
    "            if p.val < head.val:\n",
    "                ans.append(head.val)\n",
    "            else:\n",
    "                cur = p.next\n",
    "                while cur:\n",
    "                    if cur.val > p.val:\n",
    "                        ans.append(cur.val)\n",
    "                        break\n",
    "                    cur = cur.next\n",
    "                else:\n",
    "                    ans.append(0)\n",
    "                p.next = cur    # 至关重要，缩短路径\n",
    "            head = p\n",
    "\n",
    "        ans.reverse()\n",
    "        return ans\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:202003071650--2h\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: ListNode) -> List[int]:\n",
    "        if not head.next:return [0]\n",
    "        else:\n",
    "            rst=self.nextLargerNodes(head.next)\n",
    "            if head.val < head.next.val :rst.insert(0,head.next.val)\n",
    "            elif head.val == head.next.val :rst.insert(0,rst[0]) \n",
    "            else:\n",
    "                while head.next.val!=rst[0]:\n",
    "                    if not head.next.next:\n",
    "                        head=head.next\n",
    "                        break\n",
    "                    else:head.next=head.next.next\n",
    "                rst.insert(0,self.nextLargerNodes(head)[0])\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:202003071650--2h\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: ListNode) -> List[int]:\n",
    "        if not head.next:return [0]\n",
    "        else:\n",
    "            rst=self.nextLargerNodes(head.next)\n",
    "            #print(\"head=\",head,\"rst=\",rst)\n",
    "            if head.val < head.next.val :rst.insert(0,head.next.val)\n",
    "            elif head.val == head.next.val :rst.insert(0,rst[0]) \n",
    "            else:\n",
    "                if max(rst)>head.val:\n",
    "                    for i in rst:\n",
    "                        if i>head.val:\n",
    "                            rst.insert(0,i)\n",
    "                            break\n",
    "                else:rst.insert(0,0)\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: ListNode) -> List[int]:\n",
    "        if not head: return []\n",
    "        l = list()\n",
    "        self.next_larger(head, l)\n",
    "        return list(map(lambda x: x[0], l))\n",
    "\n",
    "    def next_larger(self, head, l):\n",
    "        if not head: return\n",
    "        if not head.next:\n",
    "            l.insert(0, (0, None))\n",
    "            return\n",
    "        \n",
    "        self.next_larger(head.next, l)\n",
    "\n",
    "        if head.val < head.next.val:\n",
    "            l.insert(0, (head.next.val, -len(l)))\n",
    "        else:\n",
    "            index = 0\n",
    "            while index is not None:\n",
    "                if head.val < l[index][0] or l[index][0] == 0:\n",
    "                    l.insert(0, (l[index][0], l[index][1]))\n",
    "                    return\n",
    "                index = l[index][1]     \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: ListNode) -> List[int]:\n",
    "        if not head: return []\n",
    "        l = list()\n",
    "        self.next_larger(head, l)\n",
    "        return list(map(lambda x: x[0], l))\n",
    "\n",
    "    def next_larger(self, head, l):\n",
    "        if not head: return\n",
    "        if not head.next:\n",
    "            l.insert(0, (0, None))\n",
    "            return\n",
    "        \n",
    "        self.next_larger(head.next, l)\n",
    "\n",
    "        if head.val < head.next.val:\n",
    "            l.insert(0, (head.next.val, -len(l)))\n",
    "        else:\n",
    "            index = 0\n",
    "            while index is not None:\n",
    "                if head.val < l[index][0] or l[index][0] == 0:\n",
    "                    l.insert(0, (l[index][0], l[index][1]))\n",
    "                    return\n",
    "                index = l[index][1]     \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reverse_list(self, head):\n",
    "        if head.next == None:\n",
    "            return head\n",
    "        last = self.reverse_list(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return last\n",
    "\n",
    "    def nextLargerNodes(self, head):\n",
    "        head = self.reverse_list(head)\n",
    "        stack = []\n",
    "        res = []\n",
    "        while head != None:\n",
    "            print(head.val)\n",
    "            while len(stack) != 0 and stack[-1] <= head.val:\n",
    "                stack.pop(-1)\n",
    "\n",
    "            if len(stack) == 0:\n",
    "                res.insert(0, 0)\n",
    "            else:\n",
    "                res.insert(0, stack[-1])\n",
    "            stack.append(head.val)\n",
    "            head = head.next\n",
    "        print(res)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.next = None\n",
    "        self.prev = None\n",
    "\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: ListNode) -> List[int]:\n",
    "        # revert hooking\n",
    "        prev = None\n",
    "        cur = head\n",
    "        cur.prev = None\n",
    "        while True:\n",
    "            if prev:\n",
    "                cur.prev = prev\n",
    "            prev = cur\n",
    "            if cur.next:\n",
    "                cur = cur.next\n",
    "            else:\n",
    "                break\n",
    "            \n",
    "        tail = cur\n",
    "        res = []\n",
    "        # revert traverse the List\n",
    "        cur = tail\n",
    "        walls = [cur.val]\n",
    "        res.append(0)\n",
    "        cur = cur.prev\n",
    "        while cur:\n",
    "            # print(walls)\n",
    "            if cur.val < cur.next.val:\n",
    "                res.append(cur.next.val)\n",
    "                while walls and (cur.val >= walls[-1]):\n",
    "                    walls.pop()\n",
    "                walls.append(cur.val)\n",
    "            else:\n",
    "                while walls and (cur.val >= walls[-1]):\n",
    "                    walls.pop()\n",
    "                if walls:\n",
    "                    res.append(walls[-1])\n",
    "                else:\n",
    "                    res.append(0)\n",
    "                walls.append(cur.val)\n",
    "            \n",
    "            cur = cur.prev\n",
    "        \n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getLargerStack(self, head:ListNode) -> (List[int], List[int]):\n",
    "        if not head:\n",
    "            return [], []\n",
    "        retList, maxStack = self.getLargerStack(head.next)\n",
    "        if head.next:\n",
    "            if head.val < head.next.val:\n",
    "                # 比较当前值与后一个值大小，若后一值大于当前值，将后一值存入堆栈\n",
    "                maxStack.append(head.next.val)\n",
    "                retList.insert(0, head.next.val)\n",
    "            else:\n",
    "                # 将堆栈从后往前（从近往远）遍历输出，与当前值比较\n",
    "                # 若小于当前值，继续比较\n",
    "                # 若大于当前值，则填入返回列表\n",
    "                maxVal = 0\n",
    "                while maxStack:\n",
    "                    val = maxStack.pop()\n",
    "                    if head.val < val:\n",
    "                        maxVal = val\n",
    "                        maxStack.append(val)\n",
    "                        break\n",
    "                retList.insert(0, maxVal)\n",
    "        else:\n",
    "            retList.append(0)\n",
    "        return retList, maxStack\n",
    "                        \n",
    "    def nextLargerNodes(self, head: ListNode) -> List[int]:\n",
    "        if not head:\n",
    "            return []\n",
    "        l = []\n",
    "        p = head\n",
    "        l, _ = self.getLargerStack(head)\n",
    "        return l\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: ListNode) -> List[int]:\n",
    "        s,ans = [],[]\n",
    "        if not head: return []\n",
    "        def dfs(root):\n",
    "            if not root.next: \n",
    "                ans.append(0)\n",
    "                s.append(root.val)\n",
    "                return\n",
    "            dfs(root.next)\n",
    "            while len(s) > 0 and s[-1] <= root.val: s.pop(-1)\n",
    "            if len(s) == 0: ans.append(0)\n",
    "            else: ans.append(s[-1])\n",
    "            s.append(root.val)\n",
    "        dfs(head)\n",
    "        return ans[::-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def dfs(self, head: ListNode):\n",
    "        if head is None:\n",
    "            return [[], deque()]\n",
    "        child = self.dfs(head.next)\n",
    "        min_stack = child[0]\n",
    "        ret = child[1]\n",
    "        while len(min_stack) > 0 and head.val >= min_stack[-1]:\n",
    "            min_stack.pop()\n",
    "        if len(min_stack) > 0:\n",
    "            ret.appendleft(min_stack[-1])\n",
    "        else:\n",
    "            ret.appendleft(0)\n",
    "        min_stack.append(head.val)\n",
    "        return [min_stack, ret]\n",
    "    def nextLargerNodes(self, head: ListNode) -> List[int]:\n",
    "        return [x for x in self.dfs(head)[1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: ListNode) -> List[int]:\n",
    "        stack = []\n",
    "        res = []\n",
    "\n",
    "        def get_next_node(node):\n",
    "            if node is None:\n",
    "                return\n",
    "\n",
    "            get_next_node(node.next)\n",
    "\n",
    "            while stack != [] and node.val >= stack[-1]:\n",
    "                stack.pop()\n",
    "\n",
    "            res.append(stack[-1] if stack else 0)\n",
    "            stack.append(node.val)\n",
    "\n",
    "        get_next_node(head)\n",
    "\n",
    "        return list(reversed(res))\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: ListNode) -> List[int]:\n",
    "        if not head:\n",
    "            return []\n",
    "        def reverse(head):\n",
    "            if not head or not head.next:\n",
    "                return head, head \n",
    "            p = head.next \n",
    "            qhead, qtail = reverse(p)\n",
    "            qtail.next = head \n",
    "            head.next = None \n",
    "            return qhead, head \n",
    "        head, _ = reverse(head)\n",
    "        ans, stack = [0], [head.val]\n",
    "        head = head.next \n",
    "        while head:\n",
    "            while stack and stack[-1] <= head.val:\n",
    "                stack.pop()\n",
    "            if not stack:\n",
    "                ans.append(0)\n",
    "            else:\n",
    "                ans.append(stack[-1])\n",
    "            stack.append(head.val)\n",
    "            head = head.next \n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: ListNode) -> List[int]:\n",
    "        def nodeToList(head):\n",
    "            return [head.val] + nodeToList(head.next) if head else []\n",
    "        l = nodeToList(head)\n",
    "        ans = [0 for _ in range(len(l))]\n",
    "        stack, i = [], 0\n",
    "        while i < len(l):\n",
    "            while stack and l[stack[-1]] < l[i]:\n",
    "                ans[stack.pop()] = l[i]\n",
    "            stack.append(i)\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        nums = []\n",
    "        while head:\n",
    "            nums.append(head.val)\n",
    "            head = head.next\n",
    "\n",
    "        res = [0 for _ in range(len(nums))]\n",
    "        stack = []\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            while stack and stack[-1] <= nums[i]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                res[i] = stack[-1]\n",
    "            stack.append(nums[i])\n",
    "        return res\n",
    "\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        def reverse_list(head):\n",
    "            if not head or not head.next:\n",
    "                return head\n",
    "\n",
    "            cur_head = reverse_list(head.next)\n",
    "            head.next.next = head\n",
    "            head.next = None\n",
    "\n",
    "            return cur_head\n",
    "\n",
    "        head = reverse_list(head)\n",
    "        stack = []\n",
    "        res = []\n",
    "        while head:\n",
    "            while stack and stack[-1] <= head.val:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                res.append(stack[-1])\n",
    "            else:\n",
    "                res.append(0)\n",
    "            stack.append(head.val)\n",
    "\n",
    "            head = head.next\n",
    "\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverse(self, head):\n",
    "        if head.next is None: return head\n",
    "        new_head = self.reverse(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return new_head\n",
    "\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        head = self.reverse(head)\n",
    "\n",
    "        res   = []\n",
    "        stack = []\n",
    "        while head is not None:\n",
    "            while stack and stack[-1] <= head.val:\n",
    "                stack.pop()\n",
    "            if stack: \n",
    "                res.append(stack[-1])\n",
    "            else:\n",
    "                res.append(0)\n",
    "            stack.append(head.val)\n",
    "            head = head.next\n",
    "        \n",
    "        res.reverse()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        def f(head):\n",
    "            if not head.next: return head\n",
    "            last = f(head.next)\n",
    "            head.next.next = head\n",
    "            head.next = None\n",
    "            return last\n",
    "        cur = f(head)\n",
    "        q = []\n",
    "        ans = []\n",
    "        while cur:\n",
    "            while q and q[-1]<=cur.val: q.pop()\n",
    "            ans.append(q[-1] if q else 0)\n",
    "            q.append(cur.val)\n",
    "            cur = cur.next\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    cnt = 0\n",
    "    def reverseList(self, head):\n",
    "        self.cnt += 1\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "\n",
    "        p = self.reverseList(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return p\n",
    "\n",
    "    def nextLargerNodes(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if head.next is None:\n",
    "            return [0]\n",
    "\n",
    "        p = self.reverseList(head)\n",
    "\n",
    "        stack = []\n",
    "        res = [0] * self.cnt\n",
    "        while p:\n",
    "            while stack and p.val >= stack[-1]:\n",
    "                stack.pop()\n",
    "            self.cnt -= 1\n",
    "            res[self.cnt] = 0 if not stack else stack[-1]\n",
    "            stack.append(p.val)\n",
    "            p = p.next\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        def reverse(pre,cur):\n",
    "            if not cur:\n",
    "                return ListNode(0,pre)\n",
    "            t=reverse(cur,cur.next)\n",
    "            pre.next = None\n",
    "            cur.next = pre\n",
    "            return t\n",
    "        cur_head = reverse(head,head.next)\n",
    "        cur_val = []\n",
    "        store = []\n",
    "        ans = []\n",
    "        while cur_head:\n",
    "            cur_val.append(cur_head.val)\n",
    "            cur_head = cur_head.next\n",
    "        for v in cur_val[1:]:\n",
    "            while store:\n",
    "                if store[-1] <= v:\n",
    "                    store.pop()\n",
    "                else:\n",
    "                    ans.append(store[-1])\n",
    "                    break\n",
    "            else:\n",
    "                ans.append(0)\n",
    "            store.append(v)\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        def reverse(pre,cur):\n",
    "            if not cur:\n",
    "                return ListNode(0,pre)\n",
    "            t=reverse(cur,cur.next)\n",
    "            pre.next = None\n",
    "            cur.next = pre\n",
    "            return t\n",
    "        cur_head = reverse(head,head.next)\n",
    "        cur_val = []\n",
    "        store = []\n",
    "        ans = []\n",
    "        while cur_head:\n",
    "            cur_val.append(cur_head.val)\n",
    "            cur_head = cur_head.next\n",
    "        for v in cur_val[1:]:\n",
    "            while store:\n",
    "                if store[-1] <= v:\n",
    "                    store.pop()\n",
    "                else:\n",
    "                    ans.append(store[-1])\n",
    "                    break\n",
    "            else:\n",
    "                ans.append(0)\n",
    "            store.append(v)\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\r\n",
    "# class ListNode:\r\n",
    "#     def __init__(self, val=0, next=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.next = next\r\n",
    "class Solution:\r\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\r\n",
    "        if head is None:\r\n",
    "            return []\r\n",
    "        p = head\r\n",
    "        p.last = None\r\n",
    "        last = None\r\n",
    "        while p:\r\n",
    "            last = p\r\n",
    "            if p.next:\r\n",
    "                p.next.last = p\r\n",
    "            p = p.next\r\n",
    "        \r\n",
    "        p = last\r\n",
    "        while p:\r\n",
    "            p.larger = None\r\n",
    "            q = p.next\r\n",
    "            while q and p.val >= q.val:\r\n",
    "                q = q.larger\r\n",
    "            p.larger = q\r\n",
    "            p = p.last\r\n",
    "            \r\n",
    "        p = head\r\n",
    "        res = []\r\n",
    "        while p:\r\n",
    "            res.append(0 if p.larger is None else p.larger.val)\r\n",
    "            p = p.next\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def dfs(self, current_node:ListNode, stk:List[int]):\n",
    "        if current_node is None:\n",
    "            return\n",
    "        self.dfs(current_node.next, stk)\n",
    "        current_val = current_node.val\n",
    "        while len(stk)!=0 and stk[-1] <= current_val:\n",
    "            stk.pop()\n",
    "        if len(stk) == 0:\n",
    "            current_node.val = 0\n",
    "        else:\n",
    "            current_node.val = stk[-1]\n",
    "        stk.append(current_val)\n",
    "\n",
    "\n",
    "\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        self.dfs(head, [])\n",
    "        result = []\n",
    "        while head is not None:\n",
    "            result.append(head.val)\n",
    "            head = head.next\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        def ite(root: Optional[ListNode], i: int):\n",
    "            if root.next:\n",
    "                ite(root.next, i + 1)\n",
    "            while root.next and root.val >= root.next.val:\n",
    "                root.next = root.next.next\n",
    "            ans.append(root.next.val if root.next else 0)\n",
    "        \n",
    "        ans = []\n",
    "        ite(head, 0)\n",
    "        return ans[-1::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    # 递归函数：n用来计算链表中的节点个数\n",
    "    def help(self, node, n):\n",
    "        # 遇到非空节点，需要做两件事: 1.进行递归  2.利用单调栈辅助判断\n",
    "        if node is not None:\n",
    "            # 先递归（后序遍历）\n",
    "            self.help(node.next, n+1)\n",
    "            # 利用单调栈辅助判断\n",
    "            # 若单调栈不为空，则反复弹出栈顶元素，直到栈顶元素比node.val大或栈为空\n",
    "            while(self.stack and self.stack[-1] <= node.val):\n",
    "                self.stack.pop()\n",
    "            # 若此时栈中仍存在元素，则栈顶元素是比当前第n个节点的一个更大的元素，\n",
    "            # 即self.stack[-1]是self.ans[n]所对应的下一个更大节点，修改self.ans[n]\n",
    "            if self.stack:\n",
    "                self.ans[n] = self.stack[-1]\n",
    "            # 将node.val加入栈顶，此时node.val为链表从右往左看的最小值\n",
    "            self.stack.append(node.val)\n",
    "        # 遇到空节点，初始化长度为n的答案列表\n",
    "        else:       \n",
    "            self.ans = [0] * n\n",
    "\n",
    "    # 后序遍历递归+单调栈（一次遍历）\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        self.stack = list()     # 初始化单调递减栈（栈顶元素最小），辅助整个过程\n",
    "        self.help(head, 0)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        # 递归\n",
    "        stack = []\n",
    "        res = []\n",
    "        self.next_node(res, stack, head, 0)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "    def next_node(self, res, stack, current_node, node_idx):\n",
    "        if not current_node:\n",
    "            return\n",
    "        res.append(0) \n",
    "        self.next_node(res, stack, current_node.next, node_idx + 1)\n",
    "        while stack and current_node.val >= stack[-1]:\n",
    "            stack.pop()\n",
    "        if stack:\n",
    "            res[node_idx] = stack[-1]\n",
    "        stack.append(current_node.val)\n",
    "        \n",
    "            \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        dummpy = ListNode(-1)\n",
    "        res=dummpy\n",
    "        array=head\n",
    "        # while(array):\n",
    "        backhead=self.traverseNodes(head)\n",
    "        res=[]\n",
    "        s=[]\n",
    "        while(backhead!=None):\n",
    "            while(s and s[-1]<=backhead.val):\n",
    "                s.pop()\n",
    "            if(len(s)==0):\n",
    "                res.append(0)\n",
    "            else:\n",
    "                res.append(s[-1])\n",
    "            s.append(backhead.val)\n",
    "            backhead=backhead.next\n",
    "        return res[::-1]\n",
    "    def traverseNodes(self,head:Optional[ListNode])->ListNode:\n",
    "        if(head==None or head.next==None):\n",
    "            return head\n",
    "        last=self.traverseNodes(head.next)\n",
    "        head.next.next=head\n",
    "        head.next=None\n",
    "        return last\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "import collections\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        ans = []\n",
    "        #单调栈\n",
    "        st = collections.deque()\n",
    "        def dfs(node,l):\n",
    "            if node==None:\n",
    "                #st.append(node.val)\n",
    "                nonlocal ans\n",
    "                ans = [0] * l  # l 就是链表长度\n",
    "                return \n",
    "            else:\n",
    "                dfs(node.next,l+1)\n",
    "                #t是node.val右边的数，递归返回的过程就是从右到左遍历的过程\n",
    "                while st and node.val>=st[-1]:\n",
    "                    st.pop()\n",
    "                if st:\n",
    "                    ans[l]=st[-1]\n",
    "                st.append(node.val)\n",
    "                    \n",
    "                    \n",
    "        dfs(head,0)\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        ans = []\n",
    "        st = []  # 单调栈（节点值）\n",
    "        def f(node: Optional[ListNode], i: int) -> None:\n",
    "            if node is None:\n",
    "                nonlocal ans\n",
    "                ans = [0] * i  # i 就是链表长度\n",
    "                return\n",
    "            f(node.next, i + 1)\n",
    "            while st and st[-1] <= node.val:\n",
    "                st.pop()  # 弹出无用数据\n",
    "            if st:\n",
    "                ans[i] = st[-1]  # 栈顶就是第 i 个节点的下一个更大元素\n",
    "            st.append(node.val)\n",
    "        f(head, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        def changeList(nodes):\n",
    "            if not nodes:\n",
    "                return\n",
    "            headList.append(nodes.val)\n",
    "            changeList(nodes.next)\n",
    "        headList = []\n",
    "        changeList(head)\n",
    "        n = len(headList)\n",
    "        print(headList)\n",
    "        dp = [0 for i in range(n)]\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            while stack and headList[i] > headList[stack[-1]]:\n",
    "                dp[stack[-1]] = headList[i]\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "            \n",
    "        print(dp)\n",
    "                    \n",
    "\n",
    "                \n",
    "        return  dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        ans = []\n",
    "        st = []\n",
    "        def dfs(node, i):\n",
    "            if not node:\n",
    "                nonlocal ans\n",
    "                ans = [0]*i\n",
    "                return\n",
    "            dfs(node.next, i+1)\n",
    "            nonlocal st\n",
    "            while st and node.val >= st[-1]:\n",
    "                st.pop()\n",
    "            if st:\n",
    "                ans[i] = st[-1]\n",
    "            st.append(node.val)\n",
    "        dfs(head, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    #从右往左，对于小于当前值的全部pop出去\n",
    "    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:\n",
    "        ans = []\n",
    "        st = []\n",
    "        def f(node,i):\n",
    "            if node is None:\n",
    "                nonlocal ans\n",
    "                ans = [0] * i #得到链表长度\n",
    "                return \n",
    "            f(node.next,i + 1)\n",
    "            while st and st[-1] <= node.val:\n",
    "                st.pop()\n",
    "            if st:\n",
    "                ans[i] = st[-1]\n",
    "            st.append(node.val)\n",
    "        f(head,0)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
